#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


class Color{
private:
    int num_nodes, node;
    vector<vector<int>> adj_list;
    vector<int> colors;  //颜色数组
    int num_colors;  //记录使用的颜色数量
public:
    vector<int> neighbor_count;  //邻居颜色数量
    Color(int num_nodes);
    vector<int> greedyColoring();
    void constructGraph(int u, int v);
    void reassign(int num_nodes);
};

Color::Color(int num_nodes){
    this->num_nodes=num_nodes;
    num_colors=0;
    node=0;
    adj_list.assign(num_nodes,{});
    colors.assign(num_nodes,-1);
    neighbor_count.assign(num_nodes,0);
}

void Color::constructGraph(int u, int v){
    adj_list[u].emplace_back(v);
    adj_list[v].emplace_back(u);
    return;
}

void Color::reassign(int num_nodes){
    adj_list.clear();
    colors.clear();
    neighbor_count.clear();
    this->num_nodes=num_nodes;
    num_colors=0;
    node=0;
    adj_list.assign(num_nodes,{});
    colors.assign(num_nodes,-1);
    neighbor_count.assign(num_nodes,0);
}

vector<int> Color::greedyColoring() {
    for(auto &vec: adj_list){
        sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    }
    
    for (node = 0; node < num_nodes; ++node) {
        unordered_set<int> neighbor_colors; // 用于记录邻居节点已经被涂色的颜色集合

        // 遍历节点的邻居，获取邻居节点已经被涂色的颜色
        for (int neighbor : adj_list[node]) {
            if (colors[neighbor] != -1) {
                neighbor_colors.insert(colors[neighbor]);
            }
        }

        // 为当前节点涂色
        for (int color = 0; color <= num_colors; ++color) {
            if (neighbor_colors.find(color) == neighbor_colors.end()) {
                colors[node] = color;
                break;
            }
        }

        // 更新使用的颜色数量
        num_colors = max(num_colors, colors[node] + 1);
    }
    for (node = 0; node < num_nodes; ++node) {
        unordered_set<int> neighbor_colors; // 用于记录邻居节点已经被涂色的颜色集合
        for (int neighbor : adj_list[node]) {
            neighbor_colors.insert(colors[neighbor]);
        }
        neighbor_count[node]=neighbor_colors.size();
    }
    return neighbor_count;
}

